package string.动态规划;

import java.nio.ByteBuffer;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最长回文子串.java
 * @Description TODO https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @createTime 2021年03月03日 19:35:00
 */
public class 最长回文子串 {
    /**
     * 给你一个字符串 s，找到 s 中最长的回文子串
     * <p>
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     *
     *
     * todo: 动态规划可以使用的场景
     * todo：1. 大问题的解决方案，依赖于小问题的解决方案，问题的最优解由小问题的最优解得到
     * todo：2. 问题的答案依赖于问题的规模，
     */
    public String longestPalindrome(String s) {
        //特殊状态 字符串长度为0或1的时候
        int length = s.length();
        if (length<2){
            return s;
        }
        //todo：1. 定义状态，因为是回文串的可能是任意的index为i到index为j的字符串。所以可以用dp[i][j]表示是回文串。长度为字符串的长度
        boolean[][] dp=new boolean[length][length];
        char[] charArray = s.toCharArray();
        int maxLen=1;
        int begin=0;
        //循环遍历第一次，确定dp[i][j]中的j的位置   确定末尾额字符串的位置
        for (int j = 1; j < length; j++) {
            //循环遍历第二次，确定dp[i][j]中的i的位置   确定开始字符串的位置
            for (int i = 0; i <= j; i++) {
                /**
                 * todo:2  状态转移，dp[i][j]=(dp[i+1][j-1])&&(dp[i]=dp[j])
                 * todo:2  定义边界，其中dp[i+1]和dp[j-1]最极限的时候应该是相邻间隔一个字符的两个字符 比如  aba 其中两个a相差为2，所以(j-1)+(i+1)+1<2 得到 j-i<3。
                 */
                if (charArray[i]!=charArray[j]){
                    dp[i][j]=false;
                }else {
                    //在满足dp[i]=dp[j]的同时要满足 dp[i+1][j-1] 也是回文串，上面也推导出j和i的关系  j-i<3的时候表示是最小的的回文串
                    if (j-i<3){
                        dp[i][j]=true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                //todo:3  初始化状态，在i=j的时候，dp[i][j]
                if (i==j){
                    dp[i][j]=true;
                }
                //记录最长的子串,和子串的起始位置
                if (dp[i][j]&&j - i + 1 > maxLen){
                    maxLen=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}
